package org.example.Soution003;

import java.util.Arrays;
import java.util.Collections;

public class DynamicProgrammingMaxMultiply {
    public static void main(String[] args) {
        DynamicProgrammingMaxMultiply dpm = new DynamicProgrammingMaxMultiply();
        int[] nums=new int[]{2,-5,-2,-4,3};
        System.out.println(dpm.maxProduct(nums));
    }

    public int maxProduct2(int[] nums) {
        int n=nums.length;
        int[] dpMax=new int[n];  //记录最大的
        int[] dpMin=new int[n];  //记录最小的
        int[] res=new int[n]; //记录最大的
        dpMax[0]=nums[0]; res[0]=nums[0];dpMin[0]=nums[0];
        //其实可以协同处理
        int[] tmp=new int[3];
        for(int i=1;i<n;i++){
            tmp[0]=nums[i];
            tmp[1]=dpMax[i-1]*nums[i];
            tmp[2]=dpMin[i-1]*nums[i];
            for(int x=0;x<2;x++){
                for(int y=0;y<3-x-1;y++){
                    if(tmp[y]>tmp[y+1]){
                        int temp=tmp[y];
                        tmp[y]=tmp[y+1];
                        tmp[y+1]=temp;
                    }
                }
            }
            dpMin[i]=tmp[0];
            dpMax[i]=tmp[2];
            res[i]=Math.max(res[i-1],dpMax[i]);
        }
        System.out.println(Arrays.toString(dpMax));
        System.out.println(Arrays.toString(res));
        return res[n-1];
    }

    public int maxProduct(int[] nums) {
        int maxProd = nums[0], minProd = nums[0], result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int curr = nums[i];
            // 同时计算，避免先算maxProd再算minProd时maxProd已经被更新
            int tmpMax = Math.max(curr, Math.max(maxProd * curr, minProd * curr));
            int tmpMin = Math.min(curr, Math.min(maxProd * curr, minProd * curr));

            maxProd=tmpMax;
            minProd=tmpMin;

            result = Math.max(result, maxProd);
        }

        return result;
    }
}
